package com.summer.LanQiao;
import java.util.Arrays;
//递归
public class _12 {
    static int f3(int[] arr,int begin){
        if (begin==arr.length-1) return arr[begin];
        return arr[begin]+f3(arr,begin+1);
    }
    static  String reverse(String s,int end){
        if (end==0) return ""+s.charAt(end);
        return s.charAt(end)+reverse(s,end-1);
    }
    static long feibolaqiDG(int n){
        if (n==1||n==2) return 1;
         return feibolaqiDG(n-1)+feibolaqiDG(n-2);
    }
    static  long feibolaqiXH(int n){
        long f1 = 1;
        long f2 = 1;
        if (n==1||n==2) return 1;
        long sum = 0;
        for (int i = 3; i <=n ; i++) {
             sum = f1 + f2 ;
            f1 = f2 ;
            f2 = sum ;
        }
        return sum;
    }
    static int gcd(int a,int b){
        if (b == 0) return a;
        return gcd(b,a%b);
    }
    static  void insertSort(int[] arr,int k){
        if (k==0) return;
        insertSort(arr,k-1);
        int x = arr[k];
        int index = k - 1;
        while (index>-1&&x<arr[index]){
            arr[index+1] = arr[index];
            index--;
        }
        arr[index+1] = k;
    }
    public static void main(String[] args) {
      //数组求和
        int res = f3(new int[]{1,2,3,4,5},0);
        System.out.println(res);
        System.out.println(reverse("abcdefg",6));
        //斐波拉契

        long staDG = System.currentTimeMillis();
        long numDG = feibolaqiDG(10);
        long endDG = System.currentTimeMillis();
        long sueTimeDG = endDG-staDG;
        System.out.println("递归:"+numDG+"-----用时:"+sueTimeDG);
        long staXH = System.currentTimeMillis();
        long numXH = feibolaqiXH(50);
        long endXH = System.currentTimeMillis();
        long sueTimeXH = endXH-staXH;
        System.out.println("循环:"+numXH+"-------用时:"+sueTimeXH);

        //最大公约数

        System.out.println(gcd(2,4));
        //插入排序改递归
        int[] ints = {2, 1, 3, 4, 5};
        insertSort(ints,4);
        System.out.println(Arrays.toString(ints));
    }


}
